Search for: All records

We study the sample complexity of quantum hypothesis testing, wherein the goal is to determine the minimum number of samples needed to reach a desired error probability. We characterize the sample complexity of binary quantum hypothesis testing in the symmetric and asymmetric settings, and we provide bounds on the sample complexity of multiple quantum hypothesis testing. The final part of our paper outlines and reviews how sample complexity of quantum hypothesis testing is relevant to a broad swathe of research areas and can enhance understanding of many fundamental concepts, including quantum algorithms for simulation and search, quantum learning and classification, and foundations of quantum mechanics. As such, we view our paper as an invitation to researchers coming from different communities to study and contribute to the problem of sample complexity of quantum hypothesis testing, and we outline a number of open directions for future research. 

Solving the time-dependent Schrödinger equation is an important application area for quantum algorithms. We consider Schrödinger's equation in the semi-classical regime. Here the solutions exhibit strong multiple-scale behavior due to a small parameter ℏ , in the sense that the dynamics of the quantum states and the induced observables can occur on different spatial and temporal scales. Such a Schrödinger equation finds many applications, including in Born-Oppenheimer molecular dynamics and Ehrenfest dynamics. This paper considers quantum analogues of pseudo-spectral (PS) methods on classical computers. Estimates on the gate counts in terms of ℏ and the precision ε are obtained. It is found that the number of required qubits, m , scales only logarithmically with respect to ℏ . When the solution has bounded derivatives up to order ℓ , the symmetric Trotting method has gate complexity O ( ( ε ℏ ) − 1 2 p o l y l o g ( ε − 3 2 ℓ ℏ − 1 − 1 2 ℓ ) ) , provided that the diagonal unitary operators in the pseudo-spectral methods can be implemented with p o l y ( m ) operations. When physical observables are the desired outcomes, however, the step size in the time integration can be chosen independently of ℏ . The gate complexity in this case is reduced to O ( ε − 1 2 p o l y l o g ( ε − 3 2 ℓ ℏ − 1 ) ) , with ℓ again indicating the smoothness of the solution.